package leetcode._08_dynic;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author pppppp
 * @date 2022/4/9 8:16
 * 给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
 * 回文字符串 是正着读和倒过来读一样的字符串。
 * 子字符串 是字符串中的由连续字符组成的一个序列。
 * 具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
 * <p>
 * 示例 1：
 * 输入：s = "abc"
 * 输出：3
 * 解释：三个回文子串: "a", "b", "c"
 * <p>
 * 示例 2：
 * 输入：s = "aaa"
 * 输出：6
 * 解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"
 * <p>
 * 提示：
 * 1 <= s.length <= 1000
 * s 由小写英文字母组成
 */
public class _647_回文子串 {
    @Test
    public void T_0() {
        String[] s = {"abc", "aaa"};
        int[] ans = {3, 6};
        for (int i = 0; i < s.length; i++) {
            // System.out.println(countSubstrings(s[i]) == ans[i]);
            // System.out.println(countSubstrings_1(s[i]) == ans[i]);
            // System.out.println(countSubstrings_2(s[i]) == ans[i]);
            System.out.println(countSubstrings_12(s[i]) == ans[i]);
        }
    }

    /*2. 中心扩展法*/
    public int countSubstrings_2(String s) {
        char[] ch = s.toCharArray();
        int res = s.length();
        /*1.单字母个中心*/
        for (int i = 1; i < ch.length; i++) {
            int l = i - 1, r = i + 1;
            while (l >= 0 && r < ch.length && ch[l] == ch[r]) {
                res++;
                l--;
                r++;
            }
        }
        /*2.双字母中心*/
        for (int i = 1; i < ch.length; i++) {
            int l = i - 1, r = i;
            while (l >= 0 && r < ch.length && ch[l] == ch[r]) {
                res++;
                l--;
                r++;
            }
        }
        return res;
    }

    /*1.2dp法 利用已有的检测结果 dp[i][j] 表示 从 Si-Sj是否为回文串
     *Si = Sj时， i到j的距离小于2时  dp[i][j] = 1,否则 dp[i][j] = dp[i+1][j-1]
     * Si != Sj 时，dp[i][j] = 0;
     * */
    public int countSubstrings_12(String s) {
        int n = s.length();
        int[][] dp = new int[n][n];
        char[] ch = s.toCharArray();
        for (int i = n-1; i >=0; i--) {
            dp[i][i] = 1;
            for (int j = i+1; j < n; j++) {
                if (ch[i] == ch[j]) {
                    if (j - i - 1 < 2) {
                        dp[i][j] = 1;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }
            }
        }
        int sum = 0;
        for (int k = 0; k < s.length(); k++) {
            sum += Arrays.stream(dp[k]).sum();
        }
        return sum;
    }

    /*1.dp法 利用已有的检测结果 dp[i][j] 表示 从 Si-Sj是否为回文串*/
    public int countSubstrings_1(String s) {
        int[][] dp = new int[s.length()][s.length()];
        char[] ch = s.toCharArray();
        for (int i = 0; i < s.length(); i++) {
            for (int j = 0; j <= i; j++) {
                if (ch[i] == ch[j]) {
                    if (i - j - 1 < 2) {
                        dp[j][i] = 1;
                    } else {
                        dp[j][i] = dp[j + 1][i - 1];
                    }
                }
            }
        }
        int sum = 0;
        for (int k = 0; k < s.length(); k++) {
            sum += Arrays.stream(dp[k]).sum();
        }
        return sum;
    }


    /*0.dp[i]为以Si结尾的回文串个数，对dp求和即解*/
    public int countSubstrings(String s) {
        int res = s.length();
        for (int i = 1; i < s.length(); i++) {
            String subS = s.substring(0, i + 1);
            for (int j = 0; j <= subS.length() - 2; j++) {
                res += isHuiwen(subS.substring(j));
            }
        }
        return res;
    }

    private int isHuiwen(String s) {

        int l = 0, r = s.length() - 1;
        char[] ch = s.toCharArray();
        while (l < r) {
            if (ch[l++] != ch[r--]) {
                return 0;
            }
        }
        return s.length() == 0 ? 0 : 1;
    }
}
